Search results for "Simplex algorithm"
showing 10 items of 10 documents
Two optimizing procedures for the solution of complex systems of equations: a powerful tool for modelling and simulation of metabolism
2000
Introduction Standard calculations for the evaluation of indirect calorimetry (IC) are based on two-dimensional nonlinear systems of equations. For a more sophisticated evaluation metabolic models can be used, which are described by complex systems of equations. Since the solutions are multidimensional, a concrete result must be selected by means of constraints, using optimizing procedures. These multidimensional optimizations are critical concerning processing time and reproducibility of minimum detection. Methods In order to simulate the status of metabolism of ICU patients on the basis of IC data, a complex model of metabolism was developed. The model was described by a system of equatio…
A contribution to the linear programming approach to joint cost allocation: Methodology and application
2009
Abstract The linear programming (LP) approach has been commonly proposed for joint cost allocation purposes. Within a LP framework, the allocation rules are based on a marginal analysis. Unfortunately, the additivity property which is required to completely allocate joint costs fails in presence of capacity, institutional or environmental constraints. In this paper, we first illustrate that the non allocated part can be interpreted as a type of producer’s surplus. Then, by using the information contained in the Simplex tableau we propose an original two-stage methodology based on the marginal costs and the production elasticity of input factors to achieve an additive cost allocation pattern…
Witness computation for solving geometric constraint systems
2014
International audience; In geometric constraint solving, the constraints are represented with an equation system F(U, X) = 0, where X denotes the unknowns and U denotes a set of parameters. The target solution for X is noted XT. A witness is a couple (U_W, X_W) such that F(U_W, X_W) = 0. The witness is not the target solution, but they share the same combinatorial features, even when the witness and the target lie on two distinct connected components of the solution set of F(U, X) = 0. Thus a witness enables the qualitative study of the system: the detection of over- and under-constrained systems, the decomposition into irreducible subsystems, the computation of subsystems boundaries. This …
Splines in convex sets under constraints of two‐sided inequality type in a hyperplane
2008
The problem of minimization of a smoothing functional under inequality constraints is considered in a hyperplane. The conditions of the existence of a solution are obtained and some properties of this solution are investigated. It is proved that the solution is a spline. The method for its construction is suggested. First Published Online: 14 Oct 2010
OPTIMIZATIONS FOR TENSORIAL BERNSTEIN–BASED SOLVERS BY USING POLYHEDRAL BOUNDS
2010
The tensorial Bernstein basis for multivariate polynomials in n variables has a number 3n of functions for degree 2. Consequently, computing the representation of a multivariate polynomial in the tensorial Bernstein basis is an exponential time algorithm, which makes tensorial Bernstein-based solvers impractical for systems with more than n = 6 or 7 variables. This article describes a polytope (Bernstein polytope) with a number of faces, which allows to bound a sparse, multivariate polynomial expressed in the canonical basis by solving several linear programming problems. We compare the performance of a subdivision solver using domain reductions by linear programming with a solver using a c…
Reliable Outer Bounds for the Dual Simplex Algorithm with Interval Right-hand Side
2013
International audience; In this article, we describe the reliable computation of outer bounds for linear programming problems occuring in linear relaxations derived from the Bernstein polynomials. The computation uses interval arithmetic for the Gauss-Jordan pivot steps on a simplex tableau. The resulting errors are stored as interval right hand sides. Additionally, we show how to generate a start basis for the linear programs of this type. We give details of the implementation using OpenMP and comment on numerical experiments.
A purification algorithm for semi-infinite programming
1992
Abstract In this paper we present a purification algorithm for semi-infinite linear programming. Starting with a feasible point, the algorithm either finds an improved extreme point or concludes with the unboundedness of the problem. The method is based on the solution of a sequence of linear programming problems. The study of some recession conditions has allowed us to establish a weak assumption for the finite convergence of this algorithm. Numerical results illustrating the method are given.
A comparison of simplex and simulated annealing for optimization of a new rear underrun protective device
2012
In this paper, two optimization approaches to improve the product design process have been analysed. Through the analysis of a case study, concerning the designing of a new High Energy Absorption Rear Underrun Protective Device (HEARUPD), two different optimization approaches (simplex and simulated annealing) have been compared. In the implemented optimization processes, the crash between an economy car and the rear part of a truck has been simulated by dynamic numerical (FEM) analyses. Moreover, authors have proposed the use of a suitable linear function of four variables with the purpose of reducing the multi-objective optimization processes to mono-objective ones. That has been made to s…
An LP-based hyperparameter optimization model for language modeling
2018
In order to find hyperparameters for a machine learning model, algorithms such as grid search or random search are used over the space of possible values of the models hyperparameters. These search algorithms opt the solution that minimizes a specific cost function. In language models, perplexity is one of the most popular cost functions. In this study, we propose a fractional nonlinear programming model that finds the optimal perplexity value. The special structure of the model allows us to approximate it by a linear programming model that can be solved using the well-known simplex algorithm. To the best of our knowledge, this is the first attempt to use optimization techniques to find per…
Fast Earth Mover's Distance Computation for Catadioptric Image Sequences
2016
International audience; Earth mover's distance is one of the most effective metric for comparing histograms in various image retrieval applications. The main drawback is its computational complexity which hinders its usage in various comparison tasks. We propose fast earth mover's distance computation by providing better initialization to the transportation simplex algorithm. The new approach enables faster EMD computation in Visual Memory (VM) compared to the state of the art methods. The new proposed strategy computes earth mover distance without compromising its accuracy.